#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN=10050;
struct Mat{
	int m[MAXN][MAXN];	
};
Mat mul(Mat a,Mat b){
	Mat t;
	for(int i=0;i<MAXN;i++){
		for(int j=0;j<MAXN;j++){
			t.m[i][j]=0;
			for(int k=0;k<MAXN;k++){
				t.m[i][j]+=(a.m[i][k]*b.m[k][j]);
			}
		}
	}
	return t;
}
Mat quick_pow(Mat a,int n){
	Mat t;
	//初始化为单位矩阵，相当于乘1
	for(int i=0;i<MAXN;i++){
		for(int j=0;j<MAXN;j++){
			t.m[i][j]= i==j ? 1 : 0;
		}
	}
	//跟普通快速幂一致
	while(n){
		if(n&1){
			t=mul(t,a);
		}
		n/=2;
		a=mul(a,a);
	}
	return t;
}
int main(void){

	return 0;
}
